/**
 * 描述:数据结构
 *      1.SDS：详看redis
 *      2.跳跃表:redis部分也有
 *          1.跳跃表是将链表改造成基于二分查找的数据结构，如果是一个单链表，查找数据的时间复杂度为On
 *          2.于是给单链表添加一级索引，每两个节点提取一个节点到上一级作索引层
 *          3.再层层加上索引
 *          4.比如1-8的数，分成一级索引，1-2-4-6-8，二级索引1-4-8，查找一个数据只需要二分查找就行
 *          5.时间复杂度为logn
 *          6.怎么从新节点中选取一部分提到上一层（抛硬币法）
 *              当大量的节点通过逐层比较插入原链表，上层的索引渐渐不够用，需要选取新的节点作为上一层节点，使用抛硬币法，也就是随机决定，概率50%
 *              比如插入了9，第一次抛硬币为正，到了上一层索引，第二次为负，放弃提拔
 *              跳跃表插入和删除是随机的不可预测，所以用随机方法，比如抛硬币法，大体上最后都能趋于平衡
 *          7.插入节点流程
 *              1.新节点通过层层的索引比较，找到插入位置
 *              2.修改上下链表指针插入
 *              3.抛硬币决定是否提拔，提拔了再抛硬币决定是否再提拔
 *          8.删除节点流程
 *              1.新节点通过层层比较，找到删除的节点，删除层层的索引和节点，自上而下删除
 *      3.哈希表
 *          1.根据关键码去寻找值的数据映射结构，该结构通过把关键码映射的位置去寻找存放值的地方
 *          2.可能会存在hash冲突的情况
 *          3.哈希冲突解决办法
 *              1.开放地址法
 *                  1.线性探测法：出现冲突就去寻找hash表的下一个位置，将值存放进去
 *                  2.二次探测法：不是寻找下一个hash表的位置，而是按照步长的平方取模
 *              2.链地址法
 *                  1.类似hashmap的结构，存一个节点链表，然后在链表的后面加入值
 *      4.树
 *          1.满二叉树：如果一颗二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这颗二叉树为满二叉树
 *            满二叉树深度为k，有2^k - 1 个节点
 *          2.完全二叉树：完全二叉树中，除了最底层的节点没被填满外，其它每层的节点数都达到最大值，并且最下面一层的节点都集中填满在最左边
 *            优先级队列其实是一个堆，堆就是完全二叉树，同时保证父子节点的顺序关系
 *          3.二叉搜索树：二叉搜索数是一个有序树，
 *              1.左子树上的节点值均小于它的根节点值
 *              2.右子树上的节点值均大于它的根节点值
 *              3.任意节点的左右子树也是二叉搜索树
 *          4.平衡二叉树：
 *              1.左右两个子树的高度差的绝对值不超过1
 *              2.左右两个子树也是平衡二叉树
 *          5.平衡二叉搜索树：AVL，强平衡二叉树
 *              1.左子树上的节点值均小于它的根节点值
 *              2.右子树上的节点值均大于它的根节点值
 *              3.左右两个子树的高度差的绝对值不超过1
 *          6.红黑树：弱平衡二叉树，在普通的二叉树上，对每个节点添加一个颜色属性形成的，具有以下性质
 *              1.每个节点或者是黑色，或者是红色
 *              2.根节点是黑色
 *              3.每个叶子节点（null）是黑色的
 *              4.如果一个节点是红色的，那么它的子节点必须是黑色的
 *              5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点（确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树）
 *          7.B树：B-树，平衡多路查找树，多叉树
 *              1.
 *          8.B+树：
 *              1.所有关键字存储在叶子节点，非叶子节点并不存储真正的数据
 *              2.非叶子节点存储的是索引
 *              3.所有的叶子节点按顺序排列并且用双向链表相连
 *      5.一致性哈希
 *          1.普通哈希，是采用取模算法的，将hash出来的值进行取模，然后分配到不同的节点上去，产生的问题是：如果要进行扩容，会导致原有的缓存的key的位置都发生变动，
 *            也就是说，假如这时候有一台服务器挂了，那就需要把这些key再次进行重hash，分配到还没挂掉的服务器上，很容易造成服务雪崩
 *          2.一致性hash也是采用取模的方式，但是不是对服务器数量取模，是对2 ^ 32次方取模。一致性hash算法将整个hash空间按照顺时针组成一个圆环，称为hash环；接着
 *            将各个服务器的ip或者机器名进行Hash，分配到环上，最后有key生成，进行hash，找到顺时针的第一个节点，就定位到了那台存储的服务器。
 *            优点就是：当服务器数量发生变化的时候，只需要重新定位环空间中的一小部分数据，只有部分缓存会失效，不至于将压力都同一时间集中到后端
 *          3.缺点：服务器节点太少的情况下，容易出现数据倾斜的问题，也就是被缓存的对象大部分都集中在同一个节点上，数据分配不均。所以引入了虚拟节点机制，即对每一个服务节点计算
 *            多个hash，每个计算结果的位置都放置一个此服务节点，称为虚拟节点。一个实际物理节点可以对应多个虚拟节点，虚拟节点越多，hash环上的节点就越多，缓存被均匀分布的概率就越大，
 *            hash环倾斜所带来的影响就越小，同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射
 *          4.为什么一致性hash是2^32次方的？因为服务器的Ip地址是4个8位组成
 *
 * @author Youjm
 * @created 2022/2/22 19:53
 */
public class DataStructure {

}
